1. Field
The following description relates to methods of storing and retrieving data, and more particularly, to methods of storing and retrieving data in encrypted form.
2. Description of the Related Art
Recently, incidents of leakage of important information (such as customer information) stored in a database by a hacker or an insider have frequently occurred. Accordingly, the security of information stored in a database is becoming a more important issue. In particular, when data is stored in an unreliable external server, the security of the data is at greater risk.
However, as the amount of data to be processed increases exponentially and as the demand for various services increases, the use of external servers is also increasing. Therefore, a method of safely storing a database containing user information in an unreliable external server and efficiently conducting various searches is required.
When a user stores important data in an external server, the probability that the data will be leaked or maliciously used by a server administrator or an insider is greater than when the user stores the data in his or her own database. Hence, it is essential to encrypt a database. However, if a user encrypts a database using a secret key and stores the encrypted database in an external server, the external server cannot search for data requested by the user. For this reason, methods of adding additional information, such as an index, to encrypted data and searching for necessary data using the additional information have been suggested.
Boneh and Waters (Theory of Cryptography, 2007) have suggested a cryptography-based method of searching for encrypted data supporting conjunctives, subsets, and range queries. However, this method requires too much computational power, and thus although in theory it is feasible, in practice it cannot be implemented.
Hacigumus and others (ACM SIGMOD, 2002) have suggested a bucket-based index method that can actually be applied to a database. In this method, each data in a database is encrypted, and the entire region of the data is divided into a plurality of sub-regions called buckets. Then, an index is allocated to each of the buckets. When a user transmits an index of a bucket to an external server, the external server transmits all encrypted data included in the bucket to the user. Accordingly, the user decrypts all of the received data to obtain desired data. In this method, even when the user needs only a portion of the received data, the user has to decrypt all of the received data. Consequently, the computational power required of the users system is increased.